package num239;

import java.util.*;

/**
 * @author : DuJiabao
 * @Date : 2021/2/6 10:51
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc : 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回滑动窗口中的最大值。
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 *
 * 方法：用一个LinkedList保存当前窗口的第一大元素的坐标。
 *      增加元素的时候，如果window的第一个元素已经超出窗口了，那就把它删了；
 *      逐个检查窗口尾的元素，是否小于当前元素的值，如果小于的话，后面的结果都没有它的事了，直接删除掉。直到找到比当前元素大的元素（或者没有），接到它的后面
 *      并在每次滑动窗口时，将当前最大的元素保存到result中。
 *
 */
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k) return new int[0];
        int[] result = new int[nums.length - k + 1]; // 保存结果
        Deque<Integer> window = new LinkedList<>();  // 滑动窗口，保存index

        for (int i = 0; i < nums.length; i++) {
            // 检查window的第一个元素是否已经超出滑动窗口的范围，超出的话，就直接删了
            if (!window.isEmpty() && window.peek() < i - k + 1)
                window.removeFirst(); // 删除第一个元素
            // 逐个检查当前元素是否大于队尾的元素，大于的话，直接删了
            while (!window.isEmpty() && nums[i] >= nums[window.peekLast()]) {
                window.removeLast(); // 删除最后的元素
            }
            // 在比当前元素大的地方，插入
            window.addLast(i);
            // 将结果保存
            if (i >= k - 1)
                result[i - k + 1] = nums[window.peek()];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        Solution solution = new Solution();
        int[] ints = solution.maxSlidingWindow(nums, 3);

    }
}
